|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ クリーク ： [くりーく] 【名詞】 1. (1) cleek (golf) 2. (2) creek 3. (P), (n) (1) cleek (golf)/(2) creek ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ グラフ理論 ： [ぐらふりろん] (n) graph theory ・ ラフ ： [らふ] 1. (adj,n) rough 2. (adj,n) rough ・ 理 ： [り] 【名詞】 1. reason ・ 理論 ： [りろん] 【名詞】 1. theory ・ 論 ： [ろん] 【名詞】 1. (1) argument 2. discussion 3. dispute 4. controversy 5. discourse 6. debate 7. (2) theory 8. doctrine 9. (3) essay 10. treatise 1 1. comment
グラフ理論において、無向グラフ のクリーク（）とは、頂点の部分集合 のうち、 に属するあらゆる2つの頂点を繋ぐ辺が存在する場合をいう。これはすなわち、 から誘導される部分グラフが完全だということと等価である。なお、頂点の集合ではなく、そのような部分グラフをクリークと呼ぶこともある。クリークに属する頂点数をそのクリークの大きさと言う。 与えられたグラフに指定された大きさのクリークがあるかどうかを求める問題（クリーク問題、その特殊版が最大クリーク問題）はNP完全である。 クリークの逆の概念を独立集合と呼び、クリークは必ず補グラフの独立集合と対応する。 この用語は、頂点を人、辺を「知っている」という意味としたとき、全ての人が互いに知っていることになるため ""（徒党、派閥）と名付けられた。 グラフ の最大クリークは理論上重要であり、 で表される。〔, p.3〕 == 脚注・出典 == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「クリーク (グラフ理論)」の詳細全文を読む スポンサード リンク
|